package main

import "fmt"

//寻找最长回文字符串
func main() {
	str := "helloworldlevel1l"
	//找最长回文字符串-常规解法
	re := getAllSubstring(str)
	maxPanlindLen := 0
	maxPanlindWord := ""
	for _, word := range re {
		if Ispalindrome(word) {
			if maxPanlindLen < len(word) {
				maxPanlindLen = len(word)
				maxPanlindWord = word
			}
		}
	}
	fmt.Printf("常规解法：\t字串(%s)最大回文字串是：%s，长度：%d\n", str, maxPanlindWord, maxPanlindLen)
	maxPanlindLen = 0
	maxPanlindWord = ""
	maxPanlindWord = LookPanlind_two(str)
	maxPanlindLen = len(maxPanlindWord)
	fmt.Printf("中心扩展发：\t字串(%s)最大回文字串是：%s，长度：%d\n", str, maxPanlindWord, maxPanlindLen)
}

// 中心扩展法
func LookPanlind_two(str string) (s string) {

	i, j, max, c := 0, 0, 0, 0
	for i = 0; i < len(str); i++ {
		// 回文长度为奇数
		for j = 0; (i+j) < len(str) && (i-j) >= 0; j++ {
			if str[i-j] != str[i+j] {
				break
			}

			c = 2*j + 1
		}
		if max < c {
			s = str[(i - j + 1):(i + j)]
			println("奇数", s)
			max = c
		}
		// 回文长度为偶数
		for j = 0; (i+j+1) < len(str) && (i-j) >= 0; j++ {
			if str[i-j] != str[i+j+1] {
				break
			}

			c = 2*j + 2
		}
		if max < c {
			s = str[(i - j + 1):(i + j + 1)]
			println("偶数", s)
			max = c
		}
	}
	return s
}

//得到所有的字串
func getAllSubstring(str string) (re []string) {
	for i := 0; i < len(str); i++ {
		j := len(str)
		for j = len(str); j > i; j-- {
			re = append(re, str[i:j])
		}
	}
	return re
}

//判断是否是回文字符串
func Ispalindrome(str string) bool {
	//非法输入
	if len(str) == 0 {
		return false
	}
	//定义指针
	right := len(str) - 1
	left := 0

	for i := left; i < len(str)/2; i++ {
		if str[i] != str[right] {
			return false
		}
		right--
	}
	return true
}
